/*
题目：输入二叉树的右视图
连接：https://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0
描述：请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
     如输入[1,2,4,5,3],[4,2,5,1,3]时，通过前序遍历的结果[1,2,4,5,3]和中序遍历的结果[4,2,5,1,3]可重建出以下二叉树：
解析：
    利用前序和中序先构建二叉树，然后使用层序遍历的方式，将每一层的节点放入到临时数组中，那么临时数组的最后一个元素
    就是本层的最右边元素。

*/





#include <vector>
#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型vector 先序遍历
     * @param inOrder int整型vector 中序遍历
     * @return int整型vector
     */
    struct TreeNode
    {
        int value;
        TreeNode* left;
        TreeNode* right;
        TreeNode()
            :value(0),
            left(nullptr),
            right(nullptr)
        {}
    };
    TreeNode* CreatTree(vector<int>& preOrder,int p_l,int p_r,vector<int>& inOrder,int o_l,int o_r)
    {
        if(p_l>p_r || o_l>o_r)
            return nullptr;
        TreeNode* root = new TreeNode;
        root->value = preOrder[p_l];
        int t =0;
        for(int i=o_l;i<=o_r;i++)
        {
            if(inOrder[i]==preOrder[p_l])
            {
                t=i;
                break;
            }
        }
        int leftsize = t-o_l;
        int rightsize = o_r-t;
        root->left = CreatTree(preOrder,p_l+1,p_l+leftsize,inOrder,o_l,t-1);
        root->right = CreatTree(preOrder,p_l+leftsize+1,p_r,inOrder,t+1,o_r);
        return root;
    }
    void PrintRight(vector<int>& ret,TreeNode* root)
    {
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            int size = q.size();
            vector<int> tmp;
            while(size--)
            {
                TreeNode* cur = q.front();
                q.pop();
                tmp.push_back(cur->value);
                if(cur->left!=nullptr)
                {
                    q.push(cur->left);
                }
                if(cur->right!=nullptr)
                {
                    q.push(cur->right);
                }
            }
            ret.push_back(tmp[tmp.size()-1]);
        }
    }
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        // write code here
        //建树
        TreeNode* root = CreatTree(preOrder,0,preOrder.size()-1,inOrder,0,inOrder.size()-1);
        vector<int> ret;
        PrintRight(ret,root);
        return ret;

    }
};
